High-quality random numbers have long played an important and expanding role in areas such as Monte Carlo simulations; probabilistic computing methods, for example, simulated annealing, genetic algorithms, and neural networks; computer-based gaming; and VLSI chip testing. Because the prevalent computing medium has long been the general purpose, arithmetic computer, investigation into random (more properly, pseudo-random) number generation methods has mostly centered around arithmetic algorithms. The term “random number” as used in this description is a shortened form of “pseudo-random number.”
Since random number generators (RNGs) based upon arithmetic algorithms are expensive to implement with hardware, for example, ASICs or field programmable gate arrays (FPGAs), linear feedback shift registers (LFSRs) have been popular among hardware designers for implementing RNGs. A desirable property of LFSRs is the “maximal cycle length.” The maximal cycle length property is where the cycle length is 2n−1 states (i.e., clock cycles) where n is the number of bits in the register. Even though a maximal cycle length is desirable, the random number properties of an LFSR are poor.
RNGs based upon cellular automata (CA) have the advantages of economical hardware implementation, especially when implemented on FPGAs, and highly desirable random number properties. Test batteries such as DIEHARD are commonly used to evaluate the statistical characteristics of an RNG. Known disadvantages of a CA-based RNG are: 1) the cycle length is less than the theoretical maximum for the number of bits in the CA (as compared to the LFSR RNG); and 2) as a function of the initial state of the CA, the CA-based RNG may enter into different sub-cycles, any of which could possibly be substantially shorter than the main cycle. The first disadvantage can be ameliorated to some degree by extending the length of the CA (i.e., adding cells). However, the CA RNG with additional cells must still be verified as having cycle properties of some desired length. The second disadvantage is very difficult to address because all possible starting states must be tested to detect sub-cycles.
A system and method that address the aforementioned problems, as well as other related problems, are therefore desirable.